#pragma once
//#include "pch.h"
#include "../Detour/Include/DetourNavMesh.h"
#include <cstdlib>
#include <cstdio>
#include <string>
#include "../Recast/Include/Recast.h"
#include "../Detour/Include/DetourCommon.h"
#include "../Detour/Include/DetourNavMeshQuery.h"
#include "../DetourCrowd/Include/DetourCrowd.h"
#include "../Detour/Include/DetourNavMeshBuilder.h"

static const int NAVMESHSET_MAGIC = 'M' << 24 | 'S' << 16 | 'E' << 8 | 'T'; //'MSET';
static const int NAVMESHSET_VERSION = 1;

struct NavMeshSetHeader
{
	int magic;
	int version;
	int numTiles;
	dtNavMeshParams params;
};

struct NavMeshTileHeader
{
	dtTileRef tileRef;
	int dataSize;
};

/// These are just sample areas to use consistent values across the samples.
/// The use should specify these base on his needs.
enum SamplePolyAreas
{
	SAMPLE_POLYAREA_GROUND,
	SAMPLE_POLYAREA_WATER,
	SAMPLE_POLYAREA_ROAD,
	SAMPLE_POLYAREA_DOOR,
	SAMPLE_POLYAREA_GRASS,
	SAMPLE_POLYAREA_JUMP
};
enum SamplePolyFlags
{
	SAMPLE_POLYFLAGS_WALK = 0x01,		// Ability to walk (ground, grass, road)
	SAMPLE_POLYFLAGS_SWIM = 0x02,		// Ability to swim (water).
	SAMPLE_POLYFLAGS_DOOR = 0x04,		// Ability to move through doors.
	SAMPLE_POLYFLAGS_JUMP = 0x08,		// Ability to jump.
	SAMPLE_POLYFLAGS_DISABLED = 0x10,		// Disabled polygon
	SAMPLE_POLYFLAGS_ALL = 0xffff	// All abilities.
};

enum SamplePartitionType
{
	SAMPLE_PARTITION_WATERSHED,
	SAMPLE_PARTITION_MONOTONE,
	SAMPLE_PARTITION_LAYERS
};

static const int MAX_CONVEXVOL_PTS = 12;
struct ConvexVolume
{
	float verts[MAX_CONVEXVOL_PTS * 3];
	float hmin, hmax;
	int nverts;
	int area;
};

struct BuildSettings
{
	// Cell size in world units
	float cellSize;
	// Cell height in world units
	float cellHeight;
	// Agent height in world units
	float agentHeight;
	// Agent radius in world units
	float agentRadius;
	// Agent max climb in world units
	float agentMaxClimb;
	// Agent max slope in degrees
	float agentMaxSlope;
	// Region minimum size in voxels.
	// regionMinSize = sqrt(regionMinArea)
	float regionMinSize;
	// Region merge size in voxels.
	// regionMergeSize = sqrt(regionMergeArea)
	float regionMergeSize;
	// Edge max length in world units
	float edgeMaxLen;
	// Edge max error in voxels
	float edgeMaxError;
	float vertsPerPoly;
	// Detail sample distance in voxels
	float detailSampleDist;
	// Detail sample max error in voxel heights.
	float detailSampleMaxError;
	// Partition type, see SamplePartitionType
	int partitionType;
	// Bounds of the area to mesh
	float navMeshBMin[3];
	float navMeshBMax[3];
	// Size of the tiles in voxels
	float tileSize;
};

#ifndef CHUNKYTRIMESH_H
#define CHUNKYTRIMESH_H

struct rcChunkyTriMeshNode
{
	float bmin[2];
	float bmax[2];
	int i;
	int n;
};

struct rcChunkyTriMesh
{
	inline rcChunkyTriMesh() : nodes(0), nnodes(0), tris(0), ntris(0), maxTrisPerChunk(0) {}
	inline ~rcChunkyTriMesh() { delete[] nodes; delete[] tris; }

	rcChunkyTriMeshNode* nodes;
	int nnodes;
	int* tris;
	int ntris;
	int maxTrisPerChunk;

private:
	// Explicitly disabled copy constructor and copy assignment operator.
	rcChunkyTriMesh(const rcChunkyTriMesh&);
	rcChunkyTriMesh& operator=(const rcChunkyTriMesh&);
};

struct BoundsItem
{
	float bmin[2];
	float bmax[2];
	int i;
};

static int compareItemX(const void* va, const void* vb)
{
	const BoundsItem* a = (const BoundsItem*)va;
	const BoundsItem* b = (const BoundsItem*)vb;
	if (a->bmin[0] < b->bmin[0])
		return -1;
	if (a->bmin[0] > b->bmin[0])
		return 1;
	return 0;
}

static int compareItemY(const void* va, const void* vb)
{
	const BoundsItem* a = (const BoundsItem*)va;
	const BoundsItem* b = (const BoundsItem*)vb;
	if (a->bmin[1] < b->bmin[1])
		return -1;
	if (a->bmin[1] > b->bmin[1])
		return 1;
	return 0;
}

static void calcExtends(const BoundsItem* items, const int /*nitems*/,
	const int imin, const int imax,
	float* bmin, float* bmax)
{
	bmin[0] = items[imin].bmin[0];
	bmin[1] = items[imin].bmin[1];

	bmax[0] = items[imin].bmax[0];
	bmax[1] = items[imin].bmax[1];

	for (int i = imin + 1; i < imax; ++i)
	{
		const BoundsItem& it = items[i];
		if (it.bmin[0] < bmin[0]) bmin[0] = it.bmin[0];
		if (it.bmin[1] < bmin[1]) bmin[1] = it.bmin[1];

		if (it.bmax[0] > bmax[0]) bmax[0] = it.bmax[0];
		if (it.bmax[1] > bmax[1]) bmax[1] = it.bmax[1];
	}
}

inline int longestAxis(float x, float y)
{
	return y > x ? 1 : 0;
}

static void subdivide(BoundsItem* items, int nitems, int imin, int imax, int trisPerChunk,
	int& curNode, rcChunkyTriMeshNode* nodes, const int maxNodes,
	int& curTri, int* outTris, const int* inTris)
{
	int inum = imax - imin;
	int icur = curNode;

	if (curNode >= maxNodes)
		return;

	rcChunkyTriMeshNode& node = nodes[curNode++];

	if (inum <= trisPerChunk)
	{
		// Leaf
		calcExtends(items, nitems, imin, imax, node.bmin, node.bmax);

		// Copy triangles.
		node.i = curTri;
		node.n = inum;

		for (int i = imin; i < imax; ++i)
		{
			const int* src = &inTris[items[i].i * 3];
			int* dst = &outTris[curTri * 3];
			curTri++;
			dst[0] = src[0];
			dst[1] = src[1];
			dst[2] = src[2];
		}
	}
	else
	{
		// Split
		calcExtends(items, nitems, imin, imax, node.bmin, node.bmax);

		int	axis = longestAxis(node.bmax[0] - node.bmin[0],
			node.bmax[1] - node.bmin[1]);

		if (axis == 0)
		{
			// Sort along x-axis
			qsort(items + imin, static_cast<size_t>(inum), sizeof(BoundsItem), compareItemX);
		}
		else if (axis == 1)
		{
			// Sort along y-axis
			qsort(items + imin, static_cast<size_t>(inum), sizeof(BoundsItem), compareItemY);
		}

		int isplit = imin + inum / 2;

		// Left
		subdivide(items, nitems, imin, isplit, trisPerChunk, curNode, nodes, maxNodes, curTri, outTris, inTris);
		// Right
		subdivide(items, nitems, isplit, imax, trisPerChunk, curNode, nodes, maxNodes, curTri, outTris, inTris);

		int iescape = curNode - icur;
		// Negative index means escape.
		node.i = -iescape;
	}
}

bool rcCreateChunkyTriMesh(const float* verts, const int* tris, int ntris,
	int trisPerChunk, rcChunkyTriMesh* cm)
{
	int nchunks = (ntris + trisPerChunk - 1) / trisPerChunk;

	cm->nodes = new rcChunkyTriMeshNode[nchunks * 4];
	if (!cm->nodes)
		return false;

	cm->tris = new int[ntris * 3];
	if (!cm->tris)
		return false;

	cm->ntris = ntris;

	// Build tree
	BoundsItem* items = new BoundsItem[ntris];
	if (!items)
		return false;

	for (int i = 0; i < ntris; i++)
	{
		const int* t = &tris[i * 3];
		BoundsItem& it = items[i];
		it.i = i;
		// Calc triangle XZ bounds.
		it.bmin[0] = it.bmax[0] = verts[t[0] * 3 + 0];
		it.bmin[1] = it.bmax[1] = verts[t[0] * 3 + 2];
		for (int j = 1; j < 3; ++j)
		{
			const float* v = &verts[t[j] * 3];
			if (v[0] < it.bmin[0]) it.bmin[0] = v[0];
			if (v[2] < it.bmin[1]) it.bmin[1] = v[2];

			if (v[0] > it.bmax[0]) it.bmax[0] = v[0];
			if (v[2] > it.bmax[1]) it.bmax[1] = v[2];
		}
	}

	int curTri = 0;
	int curNode = 0;
	subdivide(items, ntris, 0, ntris, trisPerChunk, curNode, cm->nodes, nchunks * 4, curTri, cm->tris, tris);

	delete[] items;

	cm->nnodes = curNode;

	// Calc max tris per node.
	cm->maxTrisPerChunk = 0;
	for (int i = 0; i < cm->nnodes; ++i)
	{
		rcChunkyTriMeshNode& node = cm->nodes[i];
		const bool isLeaf = node.i >= 0;
		if (!isLeaf) continue;
		if (node.n > cm->maxTrisPerChunk)
			cm->maxTrisPerChunk = node.n;
	}

	return true;
}

inline bool checkOverlapRect(const float amin[2], const float amax[2],
	const float bmin[2], const float bmax[2])
{
	bool overlap = true;
	overlap = (amin[0] > bmax[0] || amax[0] < bmin[0]) ? false : overlap;
	overlap = (amin[1] > bmax[1] || amax[1] < bmin[1]) ? false : overlap;
	return overlap;
}

int rcGetChunksOverlappingRect(const rcChunkyTriMesh* cm,
	float bmin[2], float bmax[2],
	int* ids, const int maxIds)
{
	// Traverse tree
	int i = 0;
	int n = 0;
	while (i < cm->nnodes)
	{
		const rcChunkyTriMeshNode* node = &cm->nodes[i];
		const bool overlap = checkOverlapRect(bmin, bmax, node->bmin, node->bmax);
		const bool isLeafNode = node->i >= 0;

		if (isLeafNode && overlap)
		{
			if (n < maxIds)
			{
				ids[n] = i;
				n++;
			}
		}

		if (overlap || isLeafNode)
			i++;
		else
		{
			const int escapeIndex = -node->i;
			i += escapeIndex;
		}
	}

	return n;
}

static bool checkOverlapSegment(const float p[2], const float q[2],
	const float bmin[2], const float bmax[2])
{
	static const float EPSILON = 1e-6f;

	float tmin = 0;
	float tmax = 1;
	float d[2];
	d[0] = q[0] - p[0];
	d[1] = q[1] - p[1];

	for (int i = 0; i < 2; i++)
	{
		if (fabsf(d[i]) < EPSILON)
		{
			// Ray is parallel to slab. No hit if origin not within slab
			if (p[i] < bmin[i] || p[i] > bmax[i])
				return false;
		}
		else
		{
			// Compute intersection t value of ray with near and far plane of slab
			float ood = 1.0f / d[i];
			float t1 = (bmin[i] - p[i]) * ood;
			float t2 = (bmax[i] - p[i]) * ood;
			if (t1 > t2) { float tmp = t1; t1 = t2; t2 = tmp; }
			if (t1 > tmin) tmin = t1;
			if (t2 < tmax) tmax = t2;
			if (tmin > tmax) return false;
		}
	}
	return true;
}

int rcGetChunksOverlappingSegment(const rcChunkyTriMesh* cm,
	float p[2], float q[2],
	int* ids, const int maxIds)
{
	// Traverse tree
	int i = 0;
	int n = 0;
	while (i < cm->nnodes)
	{
		const rcChunkyTriMeshNode* node = &cm->nodes[i];
		const bool overlap = checkOverlapSegment(p, q, node->bmin, node->bmax);
		const bool isLeafNode = node->i >= 0;

		if (isLeafNode && overlap)
		{
			if (n < maxIds)
			{
				ids[n] = i;
				n++;
			}
		}

		if (overlap || isLeafNode)
			i++;
		else
		{
			const int escapeIndex = -node->i;
			i += escapeIndex;
		}
	}

	return n;
}

#endif // CHUNKYTRIMESH_H

static char* parseRow(char* buf, char* bufEnd, char* row, int len)
{
	bool start = true;
	bool done = false;
	int n = 0;
	while (!done && buf < bufEnd)
	{
		char c = *buf;
		buf++;
		// multirow
		switch (c)
		{
		case '\\':
			break;
		case '\n':
			if (start) break;
			done = true;
			break;
		case '\r':
			break;
		case '\t':
		case ' ':
			if (start) break;
			// else falls through
		default:
			start = false;
			row[n++] = c;
			if (n >= len - 1)
				done = true;
			break;
		}
	}
	row[n] = '\0';
	return buf;
}

static int parseFace(char* row, int* data, int n, int vcnt)
{
	int j = 0;
	while (*row != '\0')
	{
		// Skip initial white space
		while (*row != '\0' && (*row == ' ' || *row == '\t'))
			row++;
		char* s = row;
		// Find vertex delimiter and terminated the string there for conversion.
		while (*row != '\0' && *row != ' ' && *row != '\t')
		{
			if (*row == '/') *row = '\0';
			row++;
		}
		if (*s == '\0')
			continue;
		int vi = atoi(s);
		data[j++] = vi < 0 ? vi + vcnt : vi - 1;
		if (j >= n) return j;
	}
	return j;
}

class rcMeshLoaderObj
{
public:
	rcMeshLoaderObj() :
		m_scale(1.0f),
		m_verts(0),
		m_tris(0),
		m_normals(0),
		m_vertCount(0),
		m_triCount(0)
	{
	}
	~rcMeshLoaderObj()
	{
		delete[] m_verts;
		delete[] m_normals;
		delete[] m_tris;
	}

	bool load(const char* filename)
	{
		char* buf = 0;
		FILE* fp = fopen(filename, "rb");
		if (!fp)
			return false;
		if (fseek(fp, 0, SEEK_END) != 0)
		{
			fclose(fp);
			return false;
		}
		long bufSize = ftell(fp);
		if (bufSize < 0)
		{
			fclose(fp);
			return false;
		}
		if (fseek(fp, 0, SEEK_SET) != 0)
		{
			fclose(fp);
			return false;
		}
		buf = new char[bufSize];
		if (!buf)
		{
			fclose(fp);
			return false;
		}
		size_t readLen = fread(buf, bufSize, 1, fp);
		fclose(fp);

		if (readLen != 1)
		{
			delete[] buf;
			return false;
		}

		bool result = readModelObj(buf, bufSize);
		delete[] buf;
		return result;
	}

	bool readModelObj(char* text, long textLen)
	{
		char* src = text;
		char* srcEnd = text + textLen;
		char row[512];
		int face[32];
		float x, y, z;
		int nv;
		int vcap = 0;
		int tcap = 0;

		while (src < srcEnd)
		{
			// Parse one row
			row[0] = '\0';
			src = parseRow(src, srcEnd, row, sizeof(row) / sizeof(char));
			// Skip comments
			if (row[0] == '#') continue;
			if (row[0] == 'v' && row[1] != 'n' && row[1] != 't')
			{
				// Vertex pos
				sscanf(row + 1, "%f %f %f", &x, &y, &z);
				addVertex(x, y, z, vcap);
			}
			if (row[0] == 'f')
			{
				// Faces
				nv = parseFace(row + 1, face, 32, m_vertCount);
				for (int i = 2; i < nv; ++i)
				{
					const int a = face[0];
					const int b = face[i - 1];
					const int c = face[i];
					if (a < 0 || a >= m_vertCount || b < 0 || b >= m_vertCount || c < 0 || c >= m_vertCount)
						continue;
					addTriangle(a, b, c, tcap);
				}
			}
		}

		setMesh(m_verts, m_tris, m_vertCount, m_triCount);

		return true;
	}

	void setMesh(float* m_verts, int* m_tris, int m_vertCount, int m_triCount)
	{
		this->m_verts = m_verts;
		this->m_tris = m_tris;
		//this->m_normals = m_normals;
		this->m_vertCount = m_vertCount;
		this->m_triCount = m_triCount;

		// Calculate normals.
		m_normals = new float[m_triCount * 3];
		for (int i = 0; i < m_triCount * 3; i += 3)
		{
			const float* v0 = &m_verts[m_tris[i] * 3];
			const float* v1 = &m_verts[m_tris[i + 1] * 3];
			const float* v2 = &m_verts[m_tris[i + 2] * 3];
			float e0[3], e1[3];
			for (int j = 0; j < 3; ++j)
			{
				e0[j] = v1[j] - v0[j];
				e1[j] = v2[j] - v0[j];
			}
			float* n = &m_normals[i];
			n[0] = e0[1] * e1[2] - e0[2] * e1[1];
			n[1] = e0[2] * e1[0] - e0[0] * e1[2];
			n[2] = e0[0] * e1[1] - e0[1] * e1[0];
			float d = sqrtf(n[0] * n[0] + n[1] * n[1] + n[2] * n[2]);
			if (d > 0)
			{
				d = 1.0f / d;
				n[0] *= d;
				n[1] *= d;
				n[2] *= d;
			}
		}
	}

	const float* getVerts() const { return m_verts; }
	const float* getNormals() const { return m_normals; }
	const int* getTris() const { return m_tris; }
	int getVertCount() const { return m_vertCount; }
	int getTriCount() const { return m_triCount; }
	const std::string& getFileName() const { return m_filename; }

private:
	// Explicitly disabled copy constructor and copy assignment operator.
	rcMeshLoaderObj(const rcMeshLoaderObj&);
	rcMeshLoaderObj& operator=(const rcMeshLoaderObj&);

	void addVertex(float x, float y, float z, int& cap)
	{
		if (m_vertCount + 1 > cap)
		{
			cap = !cap ? 8 : cap * 2;
			float* nv = new float[cap * 3];
			if (m_vertCount)
				memcpy(nv, m_verts, m_vertCount * 3 * sizeof(float));
			delete[] m_verts;
			m_verts = nv;
		}
		float* dst = &m_verts[m_vertCount * 3];
		*dst++ = x * m_scale;
		*dst++ = y * m_scale;
		*dst++ = z * m_scale;
		m_vertCount++;
	}
	void addTriangle(int a, int b, int c, int& cap)
	{
		if (m_triCount + 1 > cap)
		{
			cap = !cap ? 8 : cap * 2;
			int* nv = new int[cap * 3];
			if (m_triCount)
				memcpy(nv, m_tris, m_triCount * 3 * sizeof(int));
			delete[] m_tris;
			m_tris = nv;
		}
		int* dst = &m_tris[m_triCount * 3];
		*dst++ = a;
		*dst++ = b;
		*dst++ = c;
		m_triCount++;
	}

	std::string m_filename;
	float m_scale;
	float* m_verts;
	int* m_tris;
	float* m_normals;
	int m_vertCount;
	int m_triCount;
};

class InputGeom 
{
	rcChunkyTriMesh* m_chunkyMesh;
	rcMeshLoaderObj* m_mesh;
	float m_meshBMin[3], m_meshBMax[3];
	BuildSettings m_buildSettings;
	bool m_hasBuildSettings;

	/// @name Off-Mesh connections.
	///@{
	static const int MAX_OFFMESH_CONNECTIONS = 256;
	float m_offMeshConVerts[MAX_OFFMESH_CONNECTIONS * 3 * 2];
	float m_offMeshConRads[MAX_OFFMESH_CONNECTIONS];
	unsigned char m_offMeshConDirs[MAX_OFFMESH_CONNECTIONS];
	unsigned char m_offMeshConAreas[MAX_OFFMESH_CONNECTIONS];
	unsigned short m_offMeshConFlags[MAX_OFFMESH_CONNECTIONS];
	unsigned int m_offMeshConId[MAX_OFFMESH_CONNECTIONS];
	int m_offMeshConCount;
	///@}

	/// @name Convex Volumes.
	///@{
	static const int MAX_VOLUMES = 256;
	ConvexVolume m_volumes[MAX_VOLUMES];
	int m_volumeCount;
	///@}

public:
	InputGeom() :
		m_chunkyMesh(0),
		m_mesh(0),
		m_hasBuildSettings(false),
		m_offMeshConCount(0),
		m_volumeCount(0)
	{
	}
	~InputGeom()
	{
		delete m_chunkyMesh;
		delete m_mesh;
	}

	/// Method to return static mesh data.
	const rcMeshLoaderObj* getMesh() const { return m_mesh; }
	const float* getMeshBoundsMin() const { return m_meshBMin; }
	const float* getMeshBoundsMax() const { return m_meshBMax; }
	const float* getNavMeshBoundsMin() const { return m_hasBuildSettings ? m_buildSettings.navMeshBMin : m_meshBMin; }
	const float* getNavMeshBoundsMax() const { return m_hasBuildSettings ? m_buildSettings.navMeshBMax : m_meshBMax; }
	const rcChunkyTriMesh* getChunkyMesh() const { return m_chunkyMesh; }
	const BuildSettings* getBuildSettings() const { return m_hasBuildSettings ? &m_buildSettings : 0; }
	bool raycastMesh(float* src, float* dst, float& tmin);

	/// @name Off-Mesh connections.
	///@{
	int getOffMeshConnectionCount() const { return m_offMeshConCount; }
	const float* getOffMeshConnectionVerts() const { return m_offMeshConVerts; }
	const float* getOffMeshConnectionRads() const { return m_offMeshConRads; }
	const unsigned char* getOffMeshConnectionDirs() const { return m_offMeshConDirs; }
	const unsigned char* getOffMeshConnectionAreas() const { return m_offMeshConAreas; }
	const unsigned short* getOffMeshConnectionFlags() const { return m_offMeshConFlags; }
	const unsigned int* getOffMeshConnectionId() const { return m_offMeshConId; }
	void addOffMeshConnection(const float* spos, const float* epos, const float rad,
		unsigned char bidir, unsigned char area, unsigned short flags)
	{
		if (m_offMeshConCount >= MAX_OFFMESH_CONNECTIONS) return;
		float* v = &m_offMeshConVerts[m_offMeshConCount * 3 * 2];
		m_offMeshConRads[m_offMeshConCount] = rad;
		m_offMeshConDirs[m_offMeshConCount] = bidir;
		m_offMeshConAreas[m_offMeshConCount] = area;
		m_offMeshConFlags[m_offMeshConCount] = flags;
		m_offMeshConId[m_offMeshConCount] = 1000 + m_offMeshConCount;
		rcVcopy(&v[0], spos);
		rcVcopy(&v[3], epos);
		m_offMeshConCount++;
	}
	void deleteOffMeshConnection(int i)
	{
		m_offMeshConCount--;
		float* src = &m_offMeshConVerts[m_offMeshConCount * 3 * 2];
		float* dst = &m_offMeshConVerts[i * 3 * 2];
		rcVcopy(&dst[0], &src[0]);
		rcVcopy(&dst[3], &src[3]);
		m_offMeshConRads[i] = m_offMeshConRads[m_offMeshConCount];
		m_offMeshConDirs[i] = m_offMeshConDirs[m_offMeshConCount];
		m_offMeshConAreas[i] = m_offMeshConAreas[m_offMeshConCount];
		m_offMeshConFlags[i] = m_offMeshConFlags[m_offMeshConCount];
	}
	///@}

	/// @name Box Volumes.
	///@{
	int getConvexVolumeCount() const { return m_volumeCount; }
	const ConvexVolume* getConvexVolumes() const { return m_volumes; }
	void addConvexVolume(const float* verts, const int nverts,
		const float minh, const float maxh, unsigned char area)
	{
		if (m_volumeCount >= MAX_VOLUMES) return;
		ConvexVolume* vol = &m_volumes[m_volumeCount++];
		memset(vol, 0, sizeof(ConvexVolume));
		memcpy(vol->verts, verts, sizeof(float) * 3 * nverts);
		vol->hmin = minh;
		vol->hmax = maxh;
		vol->nverts = nverts;
		vol->area = area;
	}
	void deleteConvexVolume(int i)
	{
		m_volumeCount--;
		m_volumes[i] = m_volumes[m_volumeCount];
	}

	///@}

	bool loadMeshFile(rcContext* ctx, const char* filepath)
	{
		if (m_mesh)
		{
			delete m_chunkyMesh;
			m_chunkyMesh = 0;
			delete m_mesh;
			m_mesh = 0;
		}
		m_offMeshConCount = 0;
		m_volumeCount = 0;

		m_mesh = new rcMeshLoaderObj;
		if (!m_mesh)
		{
			ctx->log(RC_LOG_ERROR, "loadMesh: Out of memory 'm_mesh'.");
			return false;
		}
		if (!m_mesh->load(filepath))
		{
			ctx->log(RC_LOG_ERROR, "buildTiledNavigation: Could not load '%s'", filepath);
			return false;
		}

		rcCalcBounds(m_mesh->getVerts(), m_mesh->getVertCount(), m_meshBMin, m_meshBMax);

		m_chunkyMesh = new rcChunkyTriMesh;
		if (!m_chunkyMesh)
		{
			ctx->log(RC_LOG_ERROR, "buildTiledNavigation: Out of memory 'm_chunkyMesh'.");
			return false;
		}
		if (!rcCreateChunkyTriMesh(m_mesh->getVerts(), m_mesh->getTris(), m_mesh->getTriCount(), 256, m_chunkyMesh))
		{
			ctx->log(RC_LOG_ERROR, "buildTiledNavigation: Failed to build chunky mesh.");
			return false;
		}

		return true;
	}

	
	bool loadMeshData(rcContext* ctx, char* meshData, long meshDataLen)
	{
		if (m_mesh)
		{
			delete m_chunkyMesh;
			m_chunkyMesh = 0;
			delete m_mesh;
			m_mesh = 0;
		}
		m_offMeshConCount = 0;
		m_volumeCount = 0;

		m_mesh = new rcMeshLoaderObj;
		if (!m_mesh)
		{
			ctx->log(RC_LOG_ERROR, "loadMesh: Out of memory 'm_mesh'.");
			return false;
		}
		if (!m_mesh->readModelObj(meshData, meshDataLen))
		{
			ctx->log(RC_LOG_ERROR, "buildTiledNavigation: Could not load '%s'", meshData);
			return false;
		}

		rcCalcBounds(m_mesh->getVerts(), m_mesh->getVertCount(), m_meshBMin, m_meshBMax);

		m_chunkyMesh = new rcChunkyTriMesh;
		if (!m_chunkyMesh)
		{
			ctx->log(RC_LOG_ERROR, "buildTiledNavigation: Out of memory 'm_chunkyMesh'.");
			return false;
		}
		if (!rcCreateChunkyTriMesh(m_mesh->getVerts(), m_mesh->getTris(), m_mesh->getTriCount(), 256, m_chunkyMesh))
		{
			ctx->log(RC_LOG_ERROR, "buildTiledNavigation: Failed to build chunky mesh.");
			return false;
		}

		return true;
	}

	bool loadMesh(rcContext* ctx, float* m_verts, int* m_tris, int m_vertCount, int m_triCount)
	{
		if (m_mesh)
		{
			delete m_chunkyMesh;
			m_chunkyMesh = 0;
			delete m_mesh;
			m_mesh = 0;
		}
		m_offMeshConCount = 0;
		m_volumeCount = 0;

		m_mesh = new rcMeshLoaderObj;
		if (!m_mesh)
		{
			ctx->log(RC_LOG_ERROR, "loadMesh: Out of memory 'm_mesh'.");
			return false;
		}
		m_mesh->setMesh(m_verts, m_tris, m_vertCount, m_triCount);

		rcCalcBounds(m_mesh->getVerts(), m_mesh->getVertCount(), m_meshBMin, m_meshBMax);

		m_chunkyMesh = new rcChunkyTriMesh;
		if (!m_chunkyMesh)
		{
			ctx->log(RC_LOG_ERROR, "buildTiledNavigation: Out of memory 'm_chunkyMesh'.");
			return false;
		}
		if (!rcCreateChunkyTriMesh(m_mesh->getVerts(), m_mesh->getTris(), m_mesh->getTriCount(), 256, m_chunkyMesh))
		{
			ctx->log(RC_LOG_ERROR, "buildTiledNavigation: Failed to build chunky mesh.");
			return false;
		}

		return true;
	}
};

class BuildContext : public rcContext
{
public:
	BuildContext() {}

	/// Dumps the log to stdout.
	void dumpLog(const char* format, ...) {}
	/// Returns number of log messages.
	int getLogCount() const {}
	/// Returns log message text.
	const char* getLogText(const int i) const {}

protected:
	/// Virtual functions for custom implementations.
	///@{
	virtual void doResetLog() {}
	virtual void doLog(const rcLogCategory category, const char* msg, const int len) {}
	virtual void doResetTimers() {}
	virtual void doStartTimer(const rcTimerLabel label) {}
	virtual void doStopTimer(const rcTimerLabel label) {}
	virtual int doGetAccumulatedTime(const rcTimerLabel label) const { return 0; }
	///@}
};

static void calcVel(float* vel, const float* pos, const float* tgt, const float speed)
{
	dtVsub(vel, tgt, pos);
	vel[1] = 0.0;
	dtVnormalize(vel);
	dtVscale(vel, vel, speed);
}

inline bool inRange(const float* v1, const float* v2, const float r, const float h)
{
	const float dx = v2[0] - v1[0];
	const float dy = v2[1] - v1[1];
	const float dz = v2[2] - v1[2];
	return (dx * dx + dz * dz) < r * r && fabsf(dy) < h;
}

// This function checks if the path has a small U-turn, that is,
// a polygon further in the path is adjacent to the first polygon
// in the path. If that happens, a shortcut is taken.
// This can happen if the target (T) location is at tile boundary,
// and we're (S) approaching it parallel to the tile edge.
// The choice at the vertex can be arbitrary, 
//  +---+---+
//  |:::|:::|
//  +-S-+-T-+
//  |:::|   | <-- the step can end up in here, resulting U-turn path.
//  +---+---+
static int fixupShortcuts(dtPolyRef* path, int npath, dtNavMeshQuery* navQuery)
{
	if (npath < 3)
		return npath;

	// Get connected polygons
	static const int maxNeis = 16;
	dtPolyRef neis[maxNeis];
	int nneis = 0;

	const dtMeshTile* tile = 0;
	const dtPoly* poly = 0;
	if (dtStatusFailed(navQuery->getAttachedNavMesh()->getTileAndPolyByRef(path[0], &tile, &poly)))
		return npath;

	for (unsigned int k = poly->firstLink; k != DT_NULL_LINK; k = tile->links[k].next)
	{
		const dtLink* link = &tile->links[k];
		if (link->ref != 0)
		{
			if (nneis < maxNeis)
				neis[nneis++] = link->ref;
		}
	}

	// If any of the neighbour polygons is within the next few polygons
	// in the path, short cut to that polygon directly.
	static const int maxLookAhead = 6;
	int cut = 0;
	for (int i = dtMin(maxLookAhead, npath) - 1; i > 1 && cut == 0; i--) {
		for (int j = 0; j < nneis; j++)
		{
			if (path[i] == neis[j]) {
				cut = i;
				break;
			}
		}
	}
	if (cut > 1)
	{
		int offset = cut - 1;
		npath -= offset;
		for (int i = 1; i < npath; i++)
			path[i] = path[i + offset];
	}

	return npath;
}

static bool getSteerTarget(dtNavMeshQuery* navQuery, const float* startPos, const float* endPos,
	const float minTargetDist,
	const dtPolyRef* path, const int pathSize,
	float* steerPos, unsigned char& steerPosFlag, dtPolyRef& steerPosRef,
	float* outPoints = 0, int* outPointCount = 0)
{
	// Find steer target.
	static const int MAX_STEER_POINTS = 3;
	float steerPath[MAX_STEER_POINTS * 3];
	unsigned char steerPathFlags[MAX_STEER_POINTS];
	dtPolyRef steerPathPolys[MAX_STEER_POINTS];
	int nsteerPath = 0;
	navQuery->findStraightPath(startPos, endPos, path, pathSize,
		steerPath, steerPathFlags, steerPathPolys, &nsteerPath, MAX_STEER_POINTS);
	if (!nsteerPath)
		return false;

	if (outPoints && outPointCount)
	{
		*outPointCount = nsteerPath;
		for (int i = 0; i < nsteerPath; ++i)
			dtVcopy(&outPoints[i * 3], &steerPath[i * 3]);
	}


	// Find vertex far enough to steer to.
	int ns = 0;
	while (ns < nsteerPath)
	{
		// Stop at Off-Mesh link or when point is further than slop away.
		if ((steerPathFlags[ns] & DT_STRAIGHTPATH_OFFMESH_CONNECTION) ||
			!inRange(&steerPath[ns * 3], startPos, minTargetDist, 1000.0f))
			break;
		ns++;
	}
	// Failed to find good point to steer to.
	if (ns >= nsteerPath)
		return false;

	dtVcopy(steerPos, &steerPath[ns * 3]);
	steerPos[1] = startPos[1];
	steerPosFlag = steerPathFlags[ns];
	steerPosRef = steerPathPolys[ns];

	return true;
}

class Sample_SoloMesh
{
protected:
	InputGeom* m_geom;
	dtNavMesh* m_navMesh;
	dtNavMeshQuery* m_navQuery;
	BuildContext* m_ctx;

	float m_cellSize;
	float m_cellHeight;
	float m_agentHeight;
	float m_agentRadius;
	float m_agentMaxClimb;
	float m_agentMaxSlope;
	float m_regionMinSize;
	float m_regionMergeSize;
	float m_edgeMaxLen;
	float m_edgeMaxError;
	float m_vertsPerPoly;
	float m_detailSampleDist;
	float m_detailSampleMaxError;
	int m_partitionType;

	bool m_filterLowHangingObstacles;
	bool m_filterLedgeSpans;
	bool m_filterWalkableLowHeightSpans;

	bool m_keepInterResults;
	float m_totalBuildTimeMs;

	unsigned char* m_triareas;
	rcHeightfield* m_solid;
	rcCompactHeightfield* m_chf;
	rcContourSet* m_cset;
	rcPolyMesh* m_pmesh;
	rcConfig m_cfg;
	rcPolyMeshDetail* m_dmesh;

	static const int MAX_POLYS = 256;
	static const int MAX_SMOOTH = 2048;

	dtQueryFilter m_filter;

	dtStatus m_pathFindStatus;

	dtPolyRef m_startRef;
	dtPolyRef m_endRef;
	dtPolyRef m_polys[MAX_POLYS];
	int m_npolys;
	unsigned char m_straightPathFlags[MAX_POLYS];
	dtPolyRef m_straightPathPolys[MAX_POLYS];
	float m_polyPickExt[3];

	float getAgentRadius() { return m_agentRadius; }
	float getAgentHeight() { return m_agentHeight; }
	float getAgentClimb() { return m_agentMaxClimb; }

	float m_targetPos[3];
	dtPolyRef m_targetRef;

	static const int AGENT_MAX_TRAIL = 64;
	static const int MAX_AGENTS = 128;
	struct AgentTrail
	{
		float trail[AGENT_MAX_TRAIL * 3];
		int htrail;
	};
	AgentTrail m_trails[MAX_AGENTS];

	dtCrowdAgentDebugInfo m_agentDebug;

public:
	Sample_SoloMesh() :
		m_geom(0),
		m_navMesh(0),
		m_navQuery(0),
		m_filterLowHangingObstacles(true),
		m_filterLedgeSpans(true),
		m_filterWalkableLowHeightSpans(true),
		m_ctx(0)
	{
		m_ctx = new BuildContext();
		resetCommonSettings();
		m_navQuery = dtAllocNavMeshQuery();

		m_polyPickExt[0] = 8;
		m_polyPickExt[1] = 16;
		m_polyPickExt[2] = 8;
	}
	~Sample_SoloMesh()
	{
		dtFreeNavMeshQuery(m_navQuery);
		cleanup();
	}

	InputGeom* getInputGeom() { return m_geom; }
	dtNavMesh* getNavMesh() { return m_navMesh; }
	dtNavMeshQuery* getNavMeshQuery() { return m_navQuery; }
	rcContext* getCtx() { return m_ctx; }

	void setInputGeom(InputGeom* geom)
	{
		m_geom = geom;
	}

	void setBuildSettings(InputGeom* geom)
	{
		m_geom = geom;
		const BuildSettings* buildSettings = geom->getBuildSettings();
		if (buildSettings)
		{
			setBuildSettings(buildSettings);
		}
	}

	void setBuildSettings(const BuildSettings* buildSettings)
	{
		m_cellSize = buildSettings->cellSize;
		m_cellHeight = buildSettings->cellHeight;
		m_agentHeight = buildSettings->agentHeight;
		m_agentRadius = buildSettings->agentRadius;
		m_agentMaxClimb = buildSettings->agentMaxClimb;
		m_agentMaxSlope = buildSettings->agentMaxSlope;
		m_regionMinSize = buildSettings->regionMinSize;
		m_regionMergeSize = buildSettings->regionMergeSize;
		m_edgeMaxLen = buildSettings->edgeMaxLen;
		m_edgeMaxError = buildSettings->edgeMaxError;
		m_vertsPerPoly = buildSettings->vertsPerPoly;
		m_detailSampleDist = buildSettings->detailSampleDist;
		m_detailSampleMaxError = buildSettings->detailSampleMaxError;
		m_partitionType = buildSettings->partitionType;
	}

	void collectSettings(BuildSettings& settings)
	{
		settings.cellSize = m_cellSize;
		settings.cellHeight = m_cellHeight;
		settings.agentHeight = m_agentHeight;
		settings.agentRadius = m_agentRadius;
		settings.agentMaxClimb = m_agentMaxClimb;
		settings.agentMaxSlope = m_agentMaxSlope;
		settings.regionMinSize = m_regionMinSize;
		settings.regionMergeSize = m_regionMergeSize;
		settings.edgeMaxLen = m_edgeMaxLen;
		settings.edgeMaxError = m_edgeMaxError;
		settings.vertsPerPoly = m_vertsPerPoly;
		settings.detailSampleDist = m_detailSampleDist;
		settings.detailSampleMaxError = m_detailSampleMaxError;
		settings.partitionType = m_partitionType;
	}

	void resetCommonSettings()
	{
		m_cellSize = 0.3f;
		m_cellHeight = 0.2f;
		m_agentHeight = 2.0f;
		m_agentRadius = 0.6f;
		m_agentMaxClimb = 0.9f;
		m_agentMaxSlope = 45.0f;
		m_regionMinSize = 8;
		m_regionMergeSize = 20;
		m_edgeMaxLen = 12.0f;
		m_edgeMaxError = 1.3f;
		m_vertsPerPoly = 6.0f;
		m_detailSampleDist = 6.0f;
		m_detailSampleMaxError = 1.0f;
		m_partitionType = SAMPLE_PARTITION_WATERSHED;
	}

	void cleanup()
	{
		delete[] m_triareas;
		m_triareas = 0;
		rcFreeHeightField(m_solid);
		m_solid = 0;
		rcFreeCompactHeightfield(m_chf);
		m_chf = 0;
		rcFreeContourSet(m_cset);
		m_cset = 0;
		rcFreePolyMesh(m_pmesh);
		m_pmesh = 0;
		rcFreePolyMeshDetail(m_dmesh);
		m_dmesh = 0;
		dtFreeNavMesh(m_navMesh);
		m_navMesh = 0;
	}

	bool loadNavmesh(const char* path)
	{
		cleanup();

		m_navMesh = loadAll(path);
		m_navQuery = dtAllocNavMeshQuery();
		m_navQuery->init(m_navMesh, 2048);

		return m_navMesh;
	}

	dtNavMesh* loadAll(const char* path)
	{
		FILE* fp = fopen(path, "rb");
		if (!fp) return 0;

		// Read header.
		NavMeshSetHeader header;
		size_t readLen = fread(&header, sizeof(NavMeshSetHeader), 1, fp);
		if (readLen != 1)
		{
			fclose(fp);
			return 0;
		}
		if (header.magic != NAVMESHSET_MAGIC)
		{
			fclose(fp);
			return 0;
		}
		if (header.version != NAVMESHSET_VERSION)
		{
			fclose(fp);
			return 0;
		}

		dtNavMesh* mesh = dtAllocNavMesh();
		if (!mesh)
		{
			fclose(fp);
			return 0;
		}
		dtStatus status = mesh->init(&header.params);
		if (dtStatusFailed(status))
		{
			fclose(fp);
			return 0;
		}

		// Read tiles.
		for (int i = 0; i < header.numTiles; ++i)
		{
			NavMeshTileHeader tileHeader;
			readLen = fread(&tileHeader, sizeof(tileHeader), 1, fp);
			if (readLen != 1)
			{
				fclose(fp);
				return 0;
			}

			if (!tileHeader.tileRef || !tileHeader.dataSize)
				break;

			unsigned char* data = (unsigned char*)dtAlloc(tileHeader.dataSize, DT_ALLOC_PERM);
			if (!data) break;
			memset(data, 0, tileHeader.dataSize);
			readLen = fread(data, tileHeader.dataSize, 1, fp);
			if (readLen != 1)
			{
				dtFree(data);
				fclose(fp);
				return 0;
			}

			mesh->addTile(data, tileHeader.dataSize, DT_TILE_FREE_DATA, tileHeader.tileRef, 0);
		}

		fclose(fp);

		return mesh;
	}

	void saveAll(const char* path)
	{
		const dtNavMesh* mesh = m_navMesh;
		if (!mesh) return;

		FILE* fp = fopen(path, "wb");
		if (!fp)
			return;

		// Store header.
		NavMeshSetHeader header;
		header.magic = NAVMESHSET_MAGIC;
		header.version = NAVMESHSET_VERSION;
		header.numTiles = 0;
		for (int i = 0; i < mesh->getMaxTiles(); ++i)
		{
			const dtMeshTile* tile = mesh->getTile(i);
			if (!tile || !tile->header || !tile->dataSize) continue;
			header.numTiles++;
		}
		memcpy(&header.params, mesh->getParams(), sizeof(dtNavMeshParams));
		fwrite(&header, sizeof(NavMeshSetHeader), 1, fp);

		// Store tiles.
		for (int i = 0; i < mesh->getMaxTiles(); ++i)
		{
			const dtMeshTile* tile = mesh->getTile(i);
			if (!tile || !tile->header || !tile->dataSize) continue;

			NavMeshTileHeader tileHeader;
			tileHeader.tileRef = mesh->getTileRef(tile);
			tileHeader.dataSize = tile->dataSize;
			fwrite(&tileHeader, sizeof(tileHeader), 1, fp);

			fwrite(tile->data, tile->dataSize, 1, fp);
		}

		fclose(fp);
	}

	bool Build()
	{
		if (!m_geom || !m_geom->getMesh())
		{
			return false;
		}

		cleanup();

		const float* bmin = m_geom->getNavMeshBoundsMin();
		const float* bmax = m_geom->getNavMeshBoundsMax();
		const float* verts = m_geom->getMesh()->getVerts();
		const int nverts = m_geom->getMesh()->getVertCount();
		const int* tris = m_geom->getMesh()->getTris();
		const int ntris = m_geom->getMesh()->getTriCount();

		//
		// Step 1. Initialize build config.
		//

		// Init build configuration from GUI
		memset(&m_cfg, 0, sizeof(m_cfg));
		m_cfg.cs = m_cellSize;
		m_cfg.ch = m_cellHeight;
		m_cfg.walkableSlopeAngle = m_agentMaxSlope;
		m_cfg.walkableHeight = (int)ceilf(m_agentHeight / m_cfg.ch);
		m_cfg.walkableClimb = (int)floorf(m_agentMaxClimb / m_cfg.ch);
		m_cfg.walkableRadius = (int)ceilf(m_agentRadius / m_cfg.cs);
		m_cfg.maxEdgeLen = (int)(m_edgeMaxLen / m_cellSize);
		m_cfg.maxSimplificationError = m_edgeMaxError;
		m_cfg.minRegionArea = (int)rcSqr(m_regionMinSize);		// Note: area = size*size
		m_cfg.mergeRegionArea = (int)rcSqr(m_regionMergeSize);	// Note: area = size*size
		m_cfg.maxVertsPerPoly = (int)m_vertsPerPoly;
		m_cfg.detailSampleDist = m_detailSampleDist < 0.9f ? 0 : m_cellSize * m_detailSampleDist;
		m_cfg.detailSampleMaxError = m_cellHeight * m_detailSampleMaxError;

		// Set the area where the navigation will be build.
		// Here the bounds of the input mesh are used, but the
		// area could be specified by an user defined box, etc.
		rcVcopy(m_cfg.bmin, bmin);
		rcVcopy(m_cfg.bmax, bmax);
		rcCalcGridSize(m_cfg.bmin, m_cfg.bmax, m_cfg.cs, &m_cfg.width, &m_cfg.height);

		//
		// Step 2. Rasterize input polygon soup.
		//

		// Allocate voxel heightfield where we rasterize our input data to.
		m_solid = rcAllocHeightfield();
		if (!m_solid)
		{
			return false;
		}
		if (!rcCreateHeightfield(m_ctx, *m_solid, m_cfg.width, m_cfg.height, m_cfg.bmin, m_cfg.bmax, m_cfg.cs, m_cfg.ch))
		{
			//m_ctx->log(RC_LOG_ERROR, "buildNavigation: Could not create solid heightfield.");
			return false;
		}

		// Allocate array that can hold triangle area types.
		// If you have multiple meshes you need to process, allocate
		// and array which can hold the max number of triangles you need to process.
		m_triareas = new unsigned char[ntris];
		if (!m_triareas)
		{
			//m_ctx->log(RC_LOG_ERROR, "buildNavigation: Out of memory 'm_triareas' (%d).", ntris);
			return false;
		}

		// Find triangles which are walkable based on their slope and rasterize them.
		// If your input data is multiple meshes, you can transform them here, calculate
		// the are type for each of the meshes and rasterize them.
		memset(m_triareas, 0, ntris * sizeof(unsigned char));
		rcMarkWalkableTriangles(m_ctx, m_cfg.walkableSlopeAngle, verts, nverts, tris, ntris, m_triareas);
		if (!rcRasterizeTriangles(m_ctx, verts, nverts, tris, m_triareas, ntris, *m_solid, m_cfg.walkableClimb))
		{
			//m_ctx->log(RC_LOG_ERROR, "buildNavigation: Could not rasterize triangles.");
			return false;
		}

		if (!m_keepInterResults)
		{
			delete[] m_triareas;
			m_triareas = 0;
		}

		//
		// Step 3. Filter walkable surfaces.
		//

		// Once all geometry is rasterized, we do initial pass of filtering to
		// remove unwanted overhangs caused by the conservative rasterization
		// as well as filter spans where the character cannot possibly stand.
		if (m_filterLowHangingObstacles)
			rcFilterLowHangingWalkableObstacles(m_ctx, m_cfg.walkableClimb, *m_solid);
		if (m_filterLedgeSpans)
			rcFilterLedgeSpans(m_ctx, m_cfg.walkableHeight, m_cfg.walkableClimb, *m_solid);
		if (m_filterWalkableLowHeightSpans)
			rcFilterWalkableLowHeightSpans(m_ctx, m_cfg.walkableHeight, *m_solid);


		//
		// Step 4. Partition walkable surface to simple regions.
		//

		// Compact the heightfield so that it is faster to handle from now on.
		// This will result more cache coherent data as well as the neighbours
		// between walkable cells will be calculated.
		m_chf = rcAllocCompactHeightfield();
		if (!m_chf)
		{
			//m_ctx->log(RC_LOG_ERROR, "buildNavigation: Out of memory 'chf'.");
			return false;
		}
		if (!rcBuildCompactHeightfield(m_ctx, m_cfg.walkableHeight, m_cfg.walkableClimb, *m_solid, *m_chf))
		{
			//m_ctx->log(RC_LOG_ERROR, "buildNavigation: Could not build compact data.");
			return false;
		}

		if (!m_keepInterResults)
		{
			rcFreeHeightField(m_solid);
			m_solid = 0;
		}

		// Erode the walkable area by agent radius.
		if (!rcErodeWalkableArea(m_ctx, m_cfg.walkableRadius, *m_chf))
		{
			//m_ctx->log(RC_LOG_ERROR, "buildNavigation: Could not erode.");
			return false;
		}

		// (Optional) Mark areas.
		const ConvexVolume* vols = m_geom->getConvexVolumes();
		for (int i = 0; i < m_geom->getConvexVolumeCount(); ++i)
			rcMarkConvexPolyArea(m_ctx, vols[i].verts, vols[i].nverts, vols[i].hmin, vols[i].hmax, (unsigned char)vols[i].area, *m_chf);


		// Partition the heightfield so that we can use simple algorithm later to triangulate the walkable areas.
		// There are 3 partitioning methods, each with some pros and cons:
		// 1) Watershed partitioning
		//   - the classic Recast partitioning
		//   - creates the nicest tessellation
		//   - usually slowest
		//   - partitions the heightfield into nice regions without holes or overlaps
		//   - the are some corner cases where this method creates produces holes and overlaps
		//      - holes may appear when a small obstacles is close to large open area (triangulation can handle this)
		//      - overlaps may occur if you have narrow spiral corridors (i.e stairs), this make triangulation to fail
		//   * generally the best choice if you precompute the navmesh, use this if you have large open areas
		// 2) Monotone partitioning
		//   - fastest
		//   - partitions the heightfield into regions without holes and overlaps (guaranteed)
		//   - creates long thin polygons, which sometimes causes paths with detours
		//   * use this if you want fast navmesh generation
		// 3) Layer partitoining
		//   - quite fast
		//   - partitions the heighfield into non-overlapping regions
		//   - relies on the triangulation code to cope with holes (thus slower than monotone partitioning)
		//   - produces better triangles than monotone partitioning
		//   - does not have the corner cases of watershed partitioning
		//   - can be slow and create a bit ugly tessellation (still better than monotone)
		//     if you have large open areas with small obstacles (not a problem if you use tiles)
		//   * good choice to use for tiled navmesh with medium and small sized tiles

		if (m_partitionType == SAMPLE_PARTITION_WATERSHED)
		{
			// Prepare for region partitioning, by calculating distance field along the walkable surface.
			if (!rcBuildDistanceField(m_ctx, *m_chf))
			{
				//m_ctx->log(RC_LOG_ERROR, "buildNavigation: Could not build distance field.");
				return false;
			}

			// Partition the walkable surface into simple regions without holes.
			if (!rcBuildRegions(m_ctx, *m_chf, 0, m_cfg.minRegionArea, m_cfg.mergeRegionArea))
			{
				//m_ctx->log(RC_LOG_ERROR, "buildNavigation: Could not build watershed regions.");
				return false;
			}
		}
		else if (m_partitionType == SAMPLE_PARTITION_MONOTONE)
		{
			// Partition the walkable surface into simple regions without holes.
			// Monotone partitioning does not need distancefield.
			if (!rcBuildRegionsMonotone(m_ctx, *m_chf, 0, m_cfg.minRegionArea, m_cfg.mergeRegionArea))
			{
				//m_ctx->log(RC_LOG_ERROR, "buildNavigation: Could not build monotone regions.");
				return false;
			}
		}
		else // SAMPLE_PARTITION_LAYERS
		{
			// Partition the walkable surface into simple regions without holes.
			if (!rcBuildLayerRegions(m_ctx, *m_chf, 0, m_cfg.minRegionArea))
			{
				//m_ctx->log(RC_LOG_ERROR, "buildNavigation: Could not build layer regions.");
				return false;
			}
		}

		//
		// Step 5. Trace and simplify region contours.
		//

		// Create contours.
		m_cset = rcAllocContourSet();
		if (!m_cset)
		{
			//m_ctx->log(RC_LOG_ERROR, "buildNavigation: Out of memory 'cset'.");
			return false;
		}
		if (!rcBuildContours(m_ctx, *m_chf, m_cfg.maxSimplificationError, m_cfg.maxEdgeLen, *m_cset))
		{
			//m_ctx->log(RC_LOG_ERROR, "buildNavigation: Could not create contours.");
			return false;
		}

		//
		// Step 6. Build polygons mesh from contours.
		//

		// Build polygon navmesh from the contours.
		m_pmesh = rcAllocPolyMesh();
		if (!m_pmesh)
		{
			//m_ctx->log(RC_LOG_ERROR, "buildNavigation: Out of memory 'pmesh'.");
			return false;
		}
		if (!rcBuildPolyMesh(m_ctx, *m_cset, m_cfg.maxVertsPerPoly, *m_pmesh))
		{
			//m_ctx->log(RC_LOG_ERROR, "buildNavigation: Could not triangulate contours.");
			return false;
		}

		//
		// Step 7. Create detail mesh which allows to access approximate height on each polygon.
		//

		m_dmesh = rcAllocPolyMeshDetail();
		if (!m_dmesh)
		{
			//m_ctx->log(RC_LOG_ERROR, "buildNavigation: Out of memory 'pmdtl'.");
			return false;
		}

		if (!rcBuildPolyMeshDetail(m_ctx, *m_pmesh, *m_chf, m_cfg.detailSampleDist, m_cfg.detailSampleMaxError, *m_dmesh))
		{
			//m_ctx->log(RC_LOG_ERROR, "buildNavigation: Could not build detail mesh.");
			return false;
		}

		if (!m_keepInterResults)
		{
			rcFreeCompactHeightfield(m_chf);
			m_chf = 0;
			rcFreeContourSet(m_cset);
			m_cset = 0;
		}

		// At this point the navigation mesh data is ready, you can access it from m_pmesh.
		// See duDebugDrawPolyMesh or dtCreateNavMeshData as examples how to access the data.

		//
		// (Optional) Step 8. Create Detour data from Recast poly mesh.
		//

		// The GUI may allow more max points per polygon than Detour can handle.
		// Only build the detour navmesh if we do not exceed the limit.
		if (m_cfg.maxVertsPerPoly <= DT_VERTS_PER_POLYGON)
		{
			unsigned char* navData = 0;
			int navDataSize = 0;

			// Update poly flags from areas.
			for (int i = 0; i < m_pmesh->npolys; ++i)
			{
				if (m_pmesh->areas[i] == RC_WALKABLE_AREA)
					m_pmesh->areas[i] = SAMPLE_POLYAREA_GROUND;

				if (m_pmesh->areas[i] == SAMPLE_POLYAREA_GROUND ||
					m_pmesh->areas[i] == SAMPLE_POLYAREA_GRASS ||
					m_pmesh->areas[i] == SAMPLE_POLYAREA_ROAD)
				{
					m_pmesh->flags[i] = SAMPLE_POLYFLAGS_WALK;
				}
				else if (m_pmesh->areas[i] == SAMPLE_POLYAREA_WATER)
				{
					m_pmesh->flags[i] = SAMPLE_POLYFLAGS_SWIM;
				}
				else if (m_pmesh->areas[i] == SAMPLE_POLYAREA_DOOR)
				{
					m_pmesh->flags[i] = SAMPLE_POLYFLAGS_WALK | SAMPLE_POLYFLAGS_DOOR;
				}
			}


			dtNavMeshCreateParams params;
			memset(&params, 0, sizeof(params));
			params.verts = m_pmesh->verts;
			params.vertCount = m_pmesh->nverts;
			params.polys = m_pmesh->polys;
			params.polyAreas = m_pmesh->areas;
			params.polyFlags = m_pmesh->flags;
			params.polyCount = m_pmesh->npolys;
			params.nvp = m_pmesh->nvp;
			params.detailMeshes = m_dmesh->meshes;
			params.detailVerts = m_dmesh->verts;
			params.detailVertsCount = m_dmesh->nverts;
			params.detailTris = m_dmesh->tris;
			params.detailTriCount = m_dmesh->ntris;
			params.offMeshConVerts = m_geom->getOffMeshConnectionVerts();
			params.offMeshConRad = m_geom->getOffMeshConnectionRads();
			params.offMeshConDir = m_geom->getOffMeshConnectionDirs();
			params.offMeshConAreas = m_geom->getOffMeshConnectionAreas();
			params.offMeshConFlags = m_geom->getOffMeshConnectionFlags();
			params.offMeshConUserID = m_geom->getOffMeshConnectionId();
			params.offMeshConCount = m_geom->getOffMeshConnectionCount();
			params.walkableHeight = m_agentHeight;
			params.walkableRadius = m_agentRadius;
			params.walkableClimb = m_agentMaxClimb;
			rcVcopy(params.bmin, m_pmesh->bmin);
			rcVcopy(params.bmax, m_pmesh->bmax);
			params.cs = m_cfg.cs;
			params.ch = m_cfg.ch;
			params.buildBvTree = true;

			if (!dtCreateNavMeshData(&params, &navData, &navDataSize))
			{
				//m_ctx->log(RC_LOG_ERROR, "Could not build Detour navmesh.");
				return false;
			}

			m_navMesh = dtAllocNavMesh();
			if (!m_navMesh)
			{
				dtFree(navData);
				//m_ctx->log(RC_LOG_ERROR, "Could not create Detour navmesh");
				return false;
			}

			dtStatus status;

			status = m_navMesh->init(navData, navDataSize, DT_TILE_FREE_DATA);
			if (dtStatusFailed(status))
			{
				dtFree(navData);
				//m_ctx->log(RC_LOG_ERROR, "Could not init Detour navmesh");
				return false;
			}

			status = m_navQuery->init(m_navMesh, 2048);
			if (dtStatusFailed(status))
			{
				//m_ctx->log(RC_LOG_ERROR, "Could not init Detour navmesh query");
				return false;
			}
		}

		m_ctx->stopTimer(RC_TIMER_TOTAL);

		return true;
	}

	void findPathStraight(float* m_spos, float* m_epos, float* m_straightPath, int* m_nstraightPath, int m_straightPathOptions)
	{
		if (!m_navMesh)
			return;

		m_navQuery->findNearestPoly(m_spos, m_polyPickExt, &m_filter, &m_startRef, 0);
		m_navQuery->findNearestPoly(m_epos, m_polyPickExt, &m_filter, &m_endRef, 0);

		m_pathFindStatus = DT_FAILURE;

		m_navQuery->findPath(m_startRef, m_endRef, m_spos, m_epos, &m_filter, m_polys, &m_npolys, MAX_POLYS);
		*m_nstraightPath = 0;
		if (m_npolys)
		{
			// In case of partial path, make sure the end point is clamped to the last polygon.
			float epos[3];
			dtVcopy(epos, m_epos);
			if (m_polys[m_npolys - 1] != m_endRef)
				m_navQuery->closestPointOnPoly(m_polys[m_npolys - 1], m_epos, epos, 0);

			m_navQuery->findStraightPath(m_spos, epos, m_polys, m_npolys,
				m_straightPath, m_straightPathFlags,
				m_straightPathPolys, &*m_nstraightPath, MAX_POLYS, m_straightPathOptions);

			//*outPointCount = m_nstraightPath;
			/*for (int i = 0; i < m_nstraightPath; ++i)
				dtVcopy(&outPoints[i * 3], &m_straightPath[i * 3]);*/
		}
	}

	void findPathFollow(float* m_spos, float* m_epos, float* m_smoothPath, int* m_nsmoothPath, int m_straightPathOptions)
	{
		if (!m_navMesh)
			return;

		m_navQuery->findNearestPoly(m_spos, m_polyPickExt, &m_filter, &m_startRef, 0);
		m_navQuery->findNearestPoly(m_epos, m_polyPickExt, &m_filter, &m_endRef, 0);
		m_pathFindStatus = DT_FAILURE;
		m_navQuery->findPath(m_startRef, m_endRef, m_spos, m_epos, &m_filter, m_polys, &m_npolys, MAX_POLYS);
		*m_nsmoothPath = 0;

		if (m_npolys)
		{
			// Iterate over the path to find smooth path on the detail mesh surface.
			dtPolyRef polys[MAX_POLYS];
			memcpy(polys, m_polys, sizeof(dtPolyRef) * m_npolys);
			int npolys = m_npolys;

			float iterPos[3], targetPos[3];
			m_navQuery->closestPointOnPoly(m_startRef, m_spos, iterPos, 0);
			m_navQuery->closestPointOnPoly(polys[npolys - 1], m_epos, targetPos, 0);

			static const float STEP_SIZE = 0.5f;
			static const float SLOP = 0.01f;

			*m_nsmoothPath = 0;

			dtVcopy(&m_smoothPath[*m_nsmoothPath * 3], iterPos);
			(*m_nsmoothPath)++;

			// Move towards target a small advancement at a time until target reached or
			// when ran out of memory to store the path.
			while (npolys && *m_nsmoothPath < MAX_SMOOTH)
			{
				// Find location to steer towards.
				float steerPos[3];
				unsigned char steerPosFlag;
				dtPolyRef steerPosRef;

				if (!getSteerTarget(m_navQuery, iterPos, targetPos, SLOP,
					polys, npolys, steerPos, steerPosFlag, steerPosRef))
					break;

				bool endOfPath = (steerPosFlag & DT_STRAIGHTPATH_END) ? true : false;
				bool offMeshConnection = (steerPosFlag & DT_STRAIGHTPATH_OFFMESH_CONNECTION) ? true : false;

				// Find movement delta.
				float delta[3], len;
				dtVsub(delta, steerPos, iterPos);
				len = dtMathSqrtf(dtVdot(delta, delta));
				// If the steer target is end of path or off-mesh link, do not move past the location.
				if ((endOfPath || offMeshConnection) && len < STEP_SIZE)
					len = 1;
				else
					len = STEP_SIZE / len;
				float moveTgt[3];
				dtVmad(moveTgt, iterPos, delta, len);

				// Move
				float result[3];
				dtPolyRef visited[16];
				int nvisited = 0;
				m_navQuery->moveAlongSurface(polys[0], iterPos, moveTgt, &m_filter,
					result, visited, &nvisited, 16);

				npolys = dtMergeCorridorStartMoved(polys, npolys, MAX_POLYS, visited, nvisited);
				npolys = fixupShortcuts(polys, npolys, m_navQuery);

				float h = 0;
				m_navQuery->getPolyHeight(polys[0], result, &h);
				result[1] = h;
				dtVcopy(iterPos, result);

				// Handle end of path and off-mesh links when close enough.
				if (endOfPath && inRange(iterPos, steerPos, SLOP, 1.0f))
				{
					// Reached end of path.
					dtVcopy(iterPos, targetPos);
					if (*m_nsmoothPath < MAX_SMOOTH)
					{
						dtVcopy(&m_smoothPath[*m_nsmoothPath * 3], iterPos);
						(*m_nsmoothPath)++;
					}
					break;
				}
				else if (offMeshConnection && inRange(iterPos, steerPos, SLOP, 1.0f))
				{
					// Reached off-mesh connection.
					float startPos[3], endPos[3];

					// Advance the path up to and over the off-mesh connection.
					dtPolyRef prevRef = 0, polyRef = polys[0];
					int npos = 0;
					while (npos < npolys && polyRef != steerPosRef)
					{
						prevRef = polyRef;
						polyRef = polys[npos];
						npos++;
					}
					for (int i = npos; i < npolys; ++i)
						polys[i - npos] = polys[i];
					npolys -= npos;

					// Handle the connection.
					dtStatus status = m_navMesh->getOffMeshConnectionPolyEndPoints(prevRef, polyRef, startPos, endPos);
					if (dtStatusSucceed(status))
					{
						if (*m_nsmoothPath < MAX_SMOOTH)
						{
							dtVcopy(&m_smoothPath[*m_nsmoothPath * 3], startPos);
							(*m_nsmoothPath)++;
							// Hack to make the dotted path not visible during off-mesh connection.
							if (*m_nsmoothPath & 1)
							{
								dtVcopy(&m_smoothPath[*m_nsmoothPath * 3], startPos);
								(*m_nsmoothPath)++;
							}
						}
						// Move position at the other side of the off-mesh link.
						dtVcopy(iterPos, endPos);
						float eh = 0.0f;
						m_navQuery->getPolyHeight(polys[0], iterPos, &eh);
						iterPos[1] = eh;
					}
				}

				// Store results.
				if (*m_nsmoothPath < MAX_SMOOTH)
				{
					dtVcopy(&m_smoothPath[*m_nsmoothPath * 3], iterPos);
					(*m_nsmoothPath)++;
				}
			}
		}
	}

	void getDrawNavMesh(float* vertsArray, int* count)
	{
		const dtNavMesh& mesh = *getNavMesh();
		int idx = 0;
		for (int i = 0; i < mesh.getMaxTiles(); ++i)
		{
			const dtMeshTile* tile = mesh.getTile(i);
			if (!tile->header) continue;
			drawMeshTile(tile, vertsArray, idx);
		}
		*count = idx;
	}

	void drawMeshTile(const dtMeshTile* tile, float* vertsArray, int& idx)
	{
		for (int i = 0; i < tile->header->polyCount; ++i)
		{
			const dtPoly* p = &tile->polys[i];
			if (p->getType() == DT_POLYTYPE_OFFMESH_CONNECTION)	// Skip off-mesh links.
				continue;

			const dtPolyDetail* pd = &tile->detailMeshes[i];

			for (int j = 0; j < pd->triCount; ++j)
			{
				const unsigned char* t = &tile->detailTris[(pd->triBase + j) * 4];
				for (int k = 0; k < 3; ++k)
				{
					if (t[k] < p->vertCount)
					{
						const float* pos = &tile->verts[p->verts[t[k]] * 3];
						vertsArray[idx] = pos[0];
						vertsArray[idx + 1] = pos[1];
						vertsArray[idx + 2] = pos[2];
						idx += 3;
					}
					else
					{
						const float* pos = &tile->detailVerts[(pd->vertBase + t[k] - p->vertCount) * 3];
						vertsArray[idx] = pos[0];
						vertsArray[idx + 1] = pos[1];
						vertsArray[idx + 2] = pos[2];
						idx += 3;
					}
				}
			}
		}
	}

	int getDrawNavMeshCount()
	{
		const dtNavMesh& mesh = *getNavMesh();
		int idx = 0;
		for (int i = 0; i < mesh.getMaxTiles(); ++i)
		{
			const dtMeshTile* tile = mesh.getTile(i);
			if (!tile->header) continue;
			drawMeshTile(tile, idx);
		}
		return idx;
	}

	void drawMeshTile(const dtMeshTile* tile, int& idx)
	{
		for (int i = 0; i < tile->header->polyCount; ++i)
		{
			const dtPoly* p = &tile->polys[i];
			if (p->getType() == DT_POLYTYPE_OFFMESH_CONNECTION)	// Skip off-mesh links.
				continue;

			const dtPolyDetail* pd = &tile->detailMeshes[i];

			idx += pd->triCount * 9;
		}
	}
};

#if 1//这里
#define EXPORT_DLL extern "C" __declspec(dllexport) //导出dll声明
#else
#define EXPORT_DLL extern//导出so .a  不需要加声明
#endif

/*创建寻路网格实例*/
EXPORT_DLL Sample_SoloMesh* CreateSoloMesh();

/*获取构建寻路网格参数*/
EXPORT_DLL void CollectSettings(Sample_SoloMesh* sample, BuildSettings settings);

/*设置构建寻路网格参数*/
EXPORT_DLL void SetBuildSettings(Sample_SoloMesh* sample, BuildSettings settings);

/*加载网格模型.obj*/
EXPORT_DLL bool LoadMeshFile(Sample_SoloMesh* sample, const char* path);

/*加载网格模型.obj*/
EXPORT_DLL bool LoadMeshData(Sample_SoloMesh * sample, char* meshData);

/*加载网格数据 unity*/
EXPORT_DLL bool LoadMesh(Sample_SoloMesh * sample, float* m_verts, int* m_tris, int m_vertCount, int m_triCount);

/*加载已经烘焙好的网格文件.bin*/
EXPORT_DLL bool LoadNavMesh(Sample_SoloMesh * sample, const char* path);

/*保存已经烘焙好的网格文件.bin*/
EXPORT_DLL void SaveNavMesh(Sample_SoloMesh * sample, const char* path);

/*构建寻路网格*/
EXPORT_DLL bool Build(Sample_SoloMesh* sample);

/*查找直线路径*/
EXPORT_DLL void FindPathStraight(Sample_SoloMesh * sample, float* m_spos, float* m_epos, float* outPoints, int* outPointCount, int m_straightPathOptions);

/*查找跟随路径 -- 当出现坡度时不是直线行走, 而是先上坡再下坡*/
EXPORT_DLL void FindPathFollow(Sample_SoloMesh * sample, float* m_spos, float* m_epos, float* outPoints, int* outPointCount, int m_straightPathOptions);

/*释放寻路网格实例*/
EXPORT_DLL void FreeSoloMesh(Sample_SoloMesh * sample);

/*获取绘制烘焙网格*/
EXPORT_DLL void GetDrawNavMesh(Sample_SoloMesh * sample, float* vertsArray, int* vertsCount);

/*获取绘制烘焙网格顶点长度*/
EXPORT_DLL int GetDrawNavMeshCount(Sample_SoloMesh * sample);
